package leetcode;

import java.lang.reflect.Array;
import java.util.*;

/**
 * @Author:xufengxiang
 * @Date 2021/5/18 20:15
 */
public class LongestSubstringWithoutRepeatingCharacters {

    public int lengthOfLongestSubstring1(String s) {
        if (null == s || s.length() <= 0) {
            return 0;
        }

        int maxLength = 0;

        int length = s.length();
        Set<Character> set = new HashSet<>(length);
        for (int i = 0; i < length; i++) {
            set.clear();
            set.add(s.charAt(i));
            for (int j = i + 1; j < length; j++) {
                char curChar = s.charAt(j);
                if (set.contains(curChar)) {
                    break;
                }
                set.add(curChar);
            }
            if (maxLength <= set.size()) {
                maxLength = set.size();
            }
        }
        return maxLength;
    }

    public int lengthOfLongestSubstring2(String s) {
        if (null == s || s.length() <= 0) {
            return 0;
        }

        int maxLength = 0;

        int length = s.length();
        //指定窗口最左侧index
        int left = 0;
        Map<Character, Integer> map = new HashMap<>(length);
        for (int i = 0; i < s.length(); i++) {
            if (map.containsKey(s.charAt(i))) {
                //获取重复字母的index
                Integer subIndex = map.get(s.charAt(i));
                //有可能是之前的重复，所以最左侧的index必须在重复index中最大
                left = Math.max(left, subIndex+1);
            }
            map.put(s.charAt(i), i);
            maxLength = Math.max(maxLength, i - left + 1);
        }

        return maxLength;
    }

    public int lengthOfLongestSubstring3(String s) {
        if (null == s || s.length() <= 0) {
            return 0;
        }

        int maxLength = 0;
        int[] charIndexs = new int[256];
        Arrays.fill(charIndexs,0,255,-1);
        //指定窗口最左侧index
        int left = 0;
        for (int i = 0; i < s.length(); i++) {
           left = Math.max(left, charIndexs[s.charAt(i)]);
           maxLength = Math.max(maxLength, i- left +1);
           charIndexs[s.charAt(i)] = i;
        }

        return maxLength;
    }
}
